The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


6.5 The Key Schedule

An algorithm’s key schedule is the mechanism that distributes key material to the different parts of the cipher that need it, expanding the key material in the process. This is necessary for three reasons:

  There are fewer key bits provided as input to the cipher than are needed by the cipher.
  The key bits used in each round must be unique to the round in order to avoid “slide” attacks [Wag95b].
  The cipher must be secure against an attacker with partial knowledge or control over some key bits.

When key schedules are poorly designed, they often lead to strange cipher properties: large classes of equivalent keys, self-inverse keys, and so forth. These properties can often aid an attacker in a real-world attack. For example, the DES weak (self-inverse) keys have been exploited in many attacks on larger cryptographic mechanisms built from DES [Knu95a], and the S-1 [Anon95] cipher was broken due to a bad key-schedule design [Wag95a]. Even worse, they can make attacks on the cipher easier, and some attacks on the cipher will be focused directly at the key schedule, such as related-key differential attacks [KSW96, KSW97]. These attacks can be especially devastating when the cipher is used in a hash function construction.

Key schedules can be divided into several broad categories [CDN98]. In some key schedules, knowledge of a round subkey uniquely specifies bits of other round subkeys. In some ciphers the bits are just reused, as in DES, IDEA, and LOKI; and in others some manipulation of the round subkeys is required to determine the other round subkeys: e.g., CAST and SAFER. Other key schedules are designed so that knowledge of one round subkey does not directly specify bits of other round subkeys. Either the round subkey itself is used to generate the other round subkeys in some cryptographically secure manner, as in RC5 and CS-Cipher [SV98], or a one-way function is used to generate the round subkeys (sometimes the block cipher itself): e.g., Blowfish, Serpent [BAK98], ICE11 [Kwa97], and Shark.


11ICE was cryptanalyzed in [RKR98].

Some simple design principles guided our development of the key schedule for Twofish:

Design the Key Schedule for the Cipher. This is not simply a cryptographic PRNG or hash function grafted onto the cipher; the Twofish key schedule is instead an integral part of the whole cipher design.
Reuse the Same Primitives. The Twofish key schedule’s subkey generation mechanism, h, is built from the same primitives as the Twofish round function. This allowed us to apply much of the same analysis to both the round function and the subkey generation. This also makes for a relatively simple picture of the cipher and key schedule together. It is reasonable to consider one round’s operations and the derivation of its subkeys at the same time.
Use All Key Bytes the Same Way. All key material goes through h (or g, which is the same function). That is, the only way a key bit can affect the cipher is after it defines a key-dependent S-box. This allows us to analyze the properties of the key schedule in terms of the properties of the byte permutations.
Make It Hard to Attack Both S-box and Subkey Generation. The key material used to derive the key-dependent S-boxes in g is derived from the key using an RS code having properties similar to those of the MDS matrix. Deriving the key material in this way maximizes the difficulties of an attacker’s trying to mount any kind of related-key attack on the cipher, by giving him conflicting requirements between controlling the S-box keys and controlling the subkeys.

The key schedule design of some other ciphers has led to various undesirable properties. These properties, such as the existence of equivalent keys; DES-style weak, semi-weak, and quasi-weak keys; and DES-style complementation properties do not necessarily make the cipher weak. However, they tend to make it harder to use the cipher securely. With our key schedule, we can make convincing arguments that none of these properties exists.

6.5.1 Performance Issues

Key schedules vary widely in performance. The DES key schedule can be computed in less than the time required to do one encryption. The Blowfish key schedule requires the time equivalent to 521 encryptions to complete. Most other algorithms fall somewhere in the middle.

For large messages, performance of the key schedule is minor compared to performance of the encryption and decryption functions. For smaller messages, key setup can overwhelm encryption speed. In the design of Twofish, we tried to balance these two items. Our performance criteria included:

  The key schedule must be precomputable for maximal efficiency. This involves trying to minimize the amount of storage required to keep the precomputed key material.
  The key schedule must work “on the fly,” deriving each block of subkey material as it is needed, with as little required memory as possible.
  The key schedule must be reasonably efficient for hardware implementations.
  The key schedule must have minimal latency for changing keys.12

12In its comments on the AES criteria, the NSA suggested that “a goal should be that two blocks could be enciphered with different keys in virtually the same time as two blocks could be enciphered with the same key” [McD97]. The cynical reader would immediately conclude that the NSA is concerned with the efficiency of their brute-force keysearch machines. However, there axe implementations where key agility is a valid concern. Key-stretching techniques can always be used to frustrate brute-force attacks [QDD86, KSHW98]. A better defense, of course, is to always use keys too laxge to make a brute-force search practicable, and to generate them randomly.

If security were not an issue, we would design a simple key schedule where the key bits were used in some natural order, like Skipjack, or with some minimal shuffling, like DES and IDEA. However, these key schedules cause weaknesses when the block cipher is used as a one-way hash function.

If performance were not an issue, it would make sense to simply use a one-way hash function to expand the key into the subkeys and S-box entries, as is done in Khufu, Blowfish, and SEAL. However, the AES efficiency requirements make such an approach unacceptable.

Balancing these two requirements led us to design a relatively simple key schedule with a very complicated analysis.


Previous Table of Contents Next